home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Tech Arsenal 1
/
Tech Arsenal (Arsenal Computer).ISO
/
tek-04
/
aie8911.zip
/
SPECS.COL
< prev
next >
Wrap
Text File
|
1989-08-31
|
13KB
|
284 lines
NOVEMBER EXPERT TOOLBOX
Note to editor: <I> is used to mark the start of italics.
<R> is used to mark the end of italics. Do not leave these
in the text. For example, if I write
the <I>halt<R> predicate
you would put
the halt predicate
in the text with 'halt' in italics.
------------- Column starts here ---------------------------------
EXECUTABLE SPECIFICATIONS
One of the big problems in software development is the Catch 22
of system specifications. On a project of any size it is
necessary to write specs to guide the implementation. In theory,
the implementation follows the specs and the resulting system
does what you want.
However, in practice you are never 100% sure that a system meets
its specs. There is also no way of knowing if the specs
themselves are correct. This is because correct specs are those
for which a true implementation does what the user wants --
something you can't test, since the system isn't implemented yet.
One way out of this dilemma is specification testing. Put the
specifications in an executable form, for example a rapid
prototype, and run them to see if they do what you want.
Executable specs have several advantages:
* You can spot bugs in the specs early on, when the cost of
fixing them is relatively small.
* End users can see if the system appears to meet their goals
before implementation starts.
* A new development or maintenance programmer can use the
executable specs to learn about the system. Running a model
system gives you an overview that is hard to get by reading
a bunch of data flow diagrams.
However, executable specs also have drawbacks:
* The programming needed to make specs executable may not become
part of the final system. This specification programming, for
example to develop a rapid prototype, is an extra up-front
cost, which may or may not be recovered by having fewer errors
in the final system.
* The programming language gobbledygook needed to make the specs
executable also clutters them up. Instead of reading English
or looking at diagrams, you may have to read code. It may be
hard to separate the particulars used to execute the specs
from the more abstract properties desired in the final system.
To provide the advantages of executable specs while minimizing
the drawbacks -- which can not be entirely eliminated -- I have
written a specification interpreter (SI) in Prolog. Advantages of
this approach are:
* Prolog code is semi-logical in nature. In addition to
implementing executable specs, the code describes logical
properties of the system. Programming details are less visible
in Prolog code, because Prolog handles many control and data
structure details automatically.
* The specification interpreter also executes system components
described in English, by analyzing the description and using
the information to construct a simulation. This lets the SI
execute specs before the more exact and detailed Prolog has
been written, or when the user just wants a high-level view of
the system.
* The SI works on partially complete -- in fact very incomplete
-- specs, by generating and calling simulation code for the
missing parts of the system. We exploit Prolog's tools for
code generation to help the analyst check out partially
complete specs.
SOME EXAMPLES
Before we bog ourselves down in implementation details, let's
look at some examples, shown in Listing 1. Each process in the
target system is defined by a <I>stub<R>, and optionally also by
Prolog code. The stub contains some minimal information about
the process: its <I>purpose<R>, an English phrase describing
what the process does, and its <I>call<R>, a term showing how the
process is called.
When we execute a specification, the process requested directly
by the user and each subprocess called during the resulting
computation is executed using either Prolog or stub definitions.
Processes defined in Prolog are generally executed in Prolog,
while those defined by stubs are executed using stubs. (The user
may, however, use stubs instead of Prolog to obtain a detail-free
view of an executing system. For details, see the complete SI
program on the AI Expert and Instant Recall BBSs -- (301)
983-8439 for Instant Recall).
Specification 1 is a very minimal specification for checking
housing survey data. The specification interpreter recognizes
that the process is defined as a stub only, and that this stub
describes an action, rather than a branch, loop or other
specialized process. Therefore the SI turns the <I>purpose<R> of
the process over to an action simulator, which does all that can
be done with so little information: tell the user that the
process would be done at this point when the system runs.
Now suppose the systems analyst works another minute or two on
the housing specs, producing the more elaborate Specification 2.
Here the top level process is defined by Prolog as well as a
stub. Using information in the subprocess stubs, this Prolog
translates into
If the data is collected for a record, put it in the sample.
Otherwise, write an error message.
Even if you don't write Prolog, you can read it with a few
minute's practice; it's an uncluttered notation for expressing
relations among the subprocesses -- and it executes in a Prolog
interpreter.
Actually, we'll execute Specification 2 not in an ordinary Prolog
interpreter, but an enhanced one, the specification interpreter,
which looks for stubs as well as code. When we do this, we get
the second execution trace shown in Listing 1. The increased
detail of this trace reflects the increased detail of the second
spec. Notice also that the SI recognizes <I>data_collected_q<R>
as a branch, and interprets its stub accordingly.
The third example shows a process defined only by a stub.
However the <I>purpose<R> of this process describes a loop, and
the specification interpreter executes a loop, simulating the
process inside the loop.
THE EXTENDED INTERPRETER
Listing 2 shows the top level of the specification interpreter.
The top level predicate <I>do_goal<R> is essentially just a
simplified Prolog interpreter in Prolog. In fact, if you left
out the first 2 rules of <I>do_goal<R>, you would have left a
very no-frills Prolog interpreter -- one with no <I>cut<R>s or
<I>or<R>s in the rules. (You can add these features with some
additional rules for <I>do_body<R>.)
As an extended Prolog interpreter, <I>do_goal<R> has to recurse
and backtrack. <I>do_goal<R> recurses because <I>do_goal<R>
calls <I>do_body<R> and <I>do_body<R> calls <I>do_goal<R>.
<I>do_goal<R> backtracks because the Prolog rules which define it
and its helper predicates backtrack.
What transforms <I>do_goal<R> from "Prolog in Prolog" into a
specification interpreter is the first rule of <I>do_goal<R>.
This says that if there is a stub matching a Prolog goal, and it
is appropriate to use it, then interpret the stub, for example
because there is no Prolog rule matching the goal.
The top level of the stub interpreter appears in Listing 3. The
stub interpreter looks at the <I>purpose<R> of the stub, an
English sentence fragment, and decides what kind of process is
described, e.g. branch, loop, action, etc. Then the stub
interpreter calls a specialized helper procedure to interpret
that kind of process.
Listing 4 shows you how loops are executed based on stub
information. This predicate (Prolog procedure) extracts the
information it needs, such as the action inside the loop, from
the English-language <I>purpose<R> in the stub. Then it uses
this information to synthesize the Prolog code needed to simulate
the loop described in the stub. For the stub from Specification
3 in Listing 1, the generated loop code is shown in Listing 5.
If you need to generate a little code at runtime, Listing 4 shows
you how to do it in Prolog. The general plan is
* get rid of any old code that might confuse the system, using the
built-in predicate <I>abolish<R>
* Use patterns to construct the new code
* Assert the code into the Prolog database
* Call the top level goal of the new code
There are a couple details to observe in doing this:
* You can put variables in your patterns. If the variables stand
for program segments, you can define the value of those segment
variables before or after their owner patterns -- as long as
the segments are defined before you put the rules containing
them in the Prolog database.
* If you define patterns as I did, with terms of the form
<variable> = <pattern>,
it's a good idea to put parentheses around the pattern, to make
sure the '=' is performed after all operators in the pattern.
* If you define the rules of a predicate in their intended order
-- the sensible thing to do -- put them in the database with
the queuing predicate <I>assertz<R> rather than the stacking
predicates <I>asserta<R> or its synonym <I>assert<R>. (Some
Prologs make <I>assert<R> a synonym of <I>asserta<R> and some
of <I>assertz<R>; I avoid it for this reason.)
LINGUISTICS FOR ENGINEERS
Many of the helper predicates of the stub interpreter use
information from the English <I>purpose<R> in the stub. The
predicates that extract this information are in Listing 6. We
have used really hokey predicates to find the verb and object of
the stub <I>purpose<R>. We could get away with this because we
require the user to write process descriptions as the predicate
(in the grammatical sense) of a single English sentence. This
requirement still affords the analyst a lot of descriptive
freedom, but limits the amount of linguistic processing needed
for the spec interpreter. It is important to limit linguistic
requirements, so development effort can be directed to the more
crucial area of simulating additional process classes (e.g.
menus and file I/O) and data descriptions to the SI.
With the analyst restricted to sentence predicates, let's look at
the questions we have to answer from the <I>purpose<R> of a stub:
Does the stub describe a branch? A loop? Some other special
kind of process? To find out, look up the verb in a list
process-classifying words. Because we have limited the
literary creativity of the specification writer, the verb is
the first word in the <I>purpose<R>.
Is the action performed on a single item or a loop? To find
out, see if the head of the main noun phrase of the verb object
is plural. This is the first noun phrase after the verb.
The specification interpreter also has to do transform the
<I>purpose<R> into an action-completed message, to inform
the use when a process in a loop has been performed.
The code that does this is in Listing 7. Again, from a
linguistic standpoint the code is very incomplete. It
overgeneralizes regular verbs in forming the past tense
of verbs, as a small child does. The result is somewhat
inelegant, but understandable and simple to implement.
The singular rule is the most obviously incomplete -- and
for a reason. While the rule fails to find the singular of
mass nouns like <I>sand<R>, this failure is really a kind
of conservatism built into the system. For if a processed
item is identified as plural, it is processed in a loop.
By recognizing only unmistakable plurals (OK, I know it
messes up words like <I>pants<R> -- fix it if it matters)
the system simulates a loop only when there is strong evidence
for one.
AN AI DEMO FOR ANALYSTS
This specification interpreter illustrates the potential for
AI to help in the software production process. It also
illustrates how current AI tools -- in this case Prolog --
make symbolic programming easy. The whole program took
less than 2 days, although I did start with some code
from Instant Recall's Prolog Tools.
The specification interpreter also illustrates a particular
design philosophy, which I will call the Schultheisz approach, in
honor of our firm's business manager: Wait and see if you really
need something before investing in it. It would be easy to
improve the SI's natural language processing, but is that the
most important improvement to make? Instead of making every part
of the system smart, build a minimal system and let the domain
specialist tell you what should be improved. His or her
judgement is almost certainly better on this than that of an AI
expert without domain expertise. By starting with a minimal
expert system and letting the domain expert guide development,
effort goes where it most improves the system.